'''
Created on Dec 17, 2010
@author: James Lindsay

Finds overlap between targets and queries.
Requires numpy.
'''
# imports.
import sys
import numpy as np

# public definitions.
entry_dt = np.dtype([\
		('type', np.bool),\
		('ref', np.int),\
		('start', np.int),\
		('stop', np.int),\
		('info', np.int),\
		])

# private definitions.		
comb_dt = np.dtype([\
		('type', np.bool),\
		('ref', np.int),\
		('pos', np.int),\
		('backtrack', np.int),\
		])
		
ref_dt = np.dtype([\
		('start', np.int),\
		('stop', np.int),\
		])

class Overlap(object):
	'''
	Adds queries, targets to an array. Sorts the array, finds queries
	nested between target start/stops.
	t: is a numpy array of dtype=entry_dt
	q: is a numpy array of dtype=entry_dt
	nr: is an integer specifying the number of references.
	
	entry_dt:
	type: True = Target, False = Query
	ref: an integer specifying sub-divisons of query and targets.
		This is a way of dividing the problem up in many sub problems.
		Its useful in genomics to group the task by chromosomes.
	start: integer specifying start position of element.
	stop: integer specifying stop position of element.
	info: an integer which should point to a better description of 
		the element in question.
	'''
	
	def __init__(self, t, q, nr, verbose=False):
		# Save pointers.
		self.queries = q
		self.targets = t
		self.num_ref = nr
		self.verbose = verbose
		
		
		# Build sorted total array.
		self._setup_reference()
	
	def weak_overlap(self, min_ov=.0000000001):
		'''
		Finds any query which has any part that overlaps a target.
		'''
		
		#print "q"
		#print self.queries
		#print "total"
		#print self.total
		#print self.ref
		
		# Create a list of tuples containing target/query indicies.
		results = set()
		
		# Loop over each reference.
		if self.verbose == True: print "Searching for weak overlap."
		for ref_idx in range(self.ref.size):
			# Get ref info.
			ref_start = self.ref[ref_idx]['start']
			ref_stop = self.ref[ref_idx]['stop']
			
			# Get slice from total.
			current = self.total[ref_start:ref_stop]

			# Loop over current tracking open targets.
			open_t = {}
			for j in range(current.size):
				
				# check if entry is target.
				if current[j]['type'] == True:
					# entry is a target.
					
					# check if its open or close.
					if current[j]['backtrack'] in open_t:
						# this is a close.
						del open_t[current[j]['backtrack']]
					else:
						# this is an open.
						open_t[ current[j]['backtrack'] ] = True
					
				else:
					# entry is a query.
					# get its bounds.
					cur_q = self.queries[current[j]['backtrack']]
					qstart = cur_q['start']
					qstop = cur_q['stop']
					qlen = float(qstop - qstart)
				#	print "qstart", qstart, qstop
					
					# loop over open targets and add a hit.
					for tidx in open_t:
						# get start/stop of targets
						tstart = self.targets[tidx]['start']
						tstop = self.targets[tidx]['stop']
						
						# find overlap of query to target.
						if tstart < qstart:
							diff = float(tstop - qstart)
						else:
							diff = float(qstop - tstart)
							
						if diff / qlen > min_ov:
						#	print "hit,",  self.targets[tidx], cur_q
						
							# add hit.
							results.add( (tidx, current[j]['backtrack']) )
						#else:
						#	print "overlap mis", self.targets[tidx] , cur_q
			
		# return results.
		return results

	def _setup_reference(self):
		'''
		Combines targets, queries and sorts by reference.
		'''
		# Instantiate combined array.
		if self.verbose == True: print "Instantiating total array."
		size = (self.targets.size + self.queries.size) * 2
		self.total = np.zeros(size, dtype=comb_dt)
		
		# Add each element into combined array.
		if self.verbose == True: print "Filling total array."
		j = 0
		for i in range(self.targets.size):
			# Copy start.
			self.total[j]['type'] = self.targets[i]['type']
			self.total[j]['ref'] = self.targets[i]['ref']
			self.total[j]['pos'] = self.targets[i]['start']
			self.total[j]['backtrack'] = i
			j += 1
			
			# Copy stop.
			self.total[j]['type'] = self.targets[i]['type']
			self.total[j]['ref'] = self.targets[i]['ref']
			self.total[j]['pos'] = self.targets[i]['stop']
			self.total[j]['backtrack'] = i
			j += 1
			
		for i in range(self.queries.size):
			# Copy start.
			self.total[j]['type'] = self.queries[i]['type']
			self.total[j]['ref'] = self.queries[i]['ref']
			self.total[j]['pos'] = self.queries[i]['start']
			self.total[j]['backtrack'] = i
			j += 1
			
			# Copy stop.
			self.total[j]['type'] = self.queries[i]['type']
			self.total[j]['ref'] = self.queries[i]['ref']
			self.total[j]['pos'] = self.queries[i]['stop']
			self.total[j]['backtrack'] = i
			j += 1
		
		# Sort by reference then start.
		if self.verbose == True: print "Sorting total array."
		self.total.sort(order=['ref', 'pos'])

		
		# Build list of start stop spots for each reference.
		if self.verbose == True: print "Indexing total array."
		self.ref = np.zeros(self.num_ref + 1, dtype=ref_dt)
		
		# Initialize entries.
		j = 0
		pref = self.total[0]['ref']
		self.ref[j]['start'] = j
		for i in range(self.total.size):
			
			# check if we continue, or start new.
			if self.total[i]['ref'] != pref:
				# set final stop.
				self.ref[j]['stop'] = i
							
				# set start.
				pref = j
				j += 1
				self.ref[j]['start'] = i

			# set stop.
			self.ref[j]['stop'] = i

